home *** CD-ROM | disk | FTP | other *** search
/ ftp.cs.arizona.edu / ftp.cs.arizona.edu.tar / ftp.cs.arizona.edu / icon / newsgrp / group97b.txt / 000008_icon-group-sender _Wed Jul 2 23:18:27 1997.msg < prev    next >
Internet Message Format  |  2000-09-20  |  2KB
  1. Received: from kingfisher.CS.Arizona.EDU by cheltenham.cs.arizona.edu; Tue, 8 Jul 1997 08:43:06 MST
  2. Received: by kingfisher.CS.Arizona.EDU; (5.65v3.2/1.1.8.2/08Nov94-0446PM)
  3.     id AA24626; Tue, 8 Jul 1997 08:43:06 -0700
  4. Message-Id: <3.0.1.32.19970702231827.007ba100@alterdial.uu.net>
  5. X-Sender: mail08621@alterdial.uu.net
  6. X-Mailer: Windows Eudora Pro Version 3.0.1 (32)
  7. Date: Wed, 02 Jul 1997 23:18:27 -0500
  8. To: icon-group@cs.arizona.edu
  9. From: Jerry Nowlin <nowlin@nowlin.com>
  10. Subject: Re: A small puzzle
  11. Mime-Version: 1.0
  12. Content-Type: text/plain; charset="us-ascii"
  13. Errors-To: icon-group-errors@cs.arizona.edu
  14. Status: RO
  15.  
  16. >  Write a procedure lcp(s1,s2) that returns the longest common
  17. >  prefix of strings s1 and s2.  For example,
  18. >
  19. >    write(lcp("fool","foodchain"))
  20. >
  21. >  would output "foo", while
  22. >
  23. >    write(lcp("aardvark","elephant"))
  24. >
  25. >  would output "" (i.e. the null string).
  26.  
  27. I couldn't resist.  I have an Icon solution:
  28.  
  29.     # the longest common prefix procedure
  30.     procedure lcp(a,b); return a ? tab(match(b[1:*b to 0 by -1])); end
  31.  
  32. I also have a (gasp!) perl solution:
  33.  
  34.     # the longest common prefix subroutine
  35.     sub lcp { do { return $_[0] if ($_[1] =~ m/^$_[0]/); }
  36. while(chop($_[0])); }
  37.  
  38. I didn't attempt to optimize either to use the shortest string as the
  39. pattern, but that would make both more efficient and is trivial to do.
  40. It's not as clean looking though and wouldn't fit on one line.  I tested
  41. both of these on win95 and got the same results.  I don't have a good way
  42. to compare speed or efficiency though.  I reckon Icon wins since it took
  43. less characters :-)
  44.  
  45. Jerry Nowlin
  46.  
  47.  
  48. Jerry Nowlin
  49. nowlin@nowlin.com
  50. http://www.xnet.com/~nowlin/
  51.